package solution

import (
	"fmt"
	"myleecode/solution/common"
	"sort"
)

// 50. 求幂 Pow(x,n)
func Leecode50_myPow(x float64, n int) float64 {
	// 非递归
	if n == 0 {
		return 1
	} else if n > 0 {
		s := x
		for n > 1 {
			s = s * x
			n--
		}
		return s
	}
	s := x
	n = -1 * n
	for n > 1 {
		s = s * x
		n--
	}

	return 1.0 / s
}

// 51. N皇后
func Leecode51_solveNQueen(n int) [][]string {
	matrix := make([][]byte, n)
	for i:=0; i<n; i++ {
		matrix[i] = make([]byte, n)
		for j:=0; j<n; j++ {
			matrix[i][j] = '.'
		}
	}
	var result [][]string
	var solve func(row int)
	var valid func(row, col int) bool

	maxtrixToStringSlice := func(m [][]byte) []string {
		a := make([]string, n)
		for i:=0; i<n; i++ {
			a[i] = string(m[i])
		}
		return a
	}

	valid = func(row, col int) bool {
		for i:=0; i<row; i++ {
			if matrix[i][col] == 'Q' {
				return false
			}
		}
		i, j := row-1, col+1
		for {
			if i<0 || j>=n {
				break
			}
			if matrix[i][j] == 'Q' {
				return false
			}
			i--
			j++
		}
		i, j = row-1, col-1
		for {
			if i<0 || j<0 {
				break
			}
			if matrix[i][j] == 'Q' {
				return false
			}
			i--
			j--
		}
		return  true
	}

	solve = func(row int) {
		if row == n {
			result = append(result, maxtrixToStringSlice(matrix))
			return
		}
		for col:=0; col<n; col++ {
			if valid(row, col) {
				matrix[row][col] = 'Q'
				solve(row+1)
				matrix[row][col] = '.'
			}
		}
	}

	solve(0)
	return result
}

// 52. N皇后：返回解决方案数量
// 采取回溯递归方法

func Leecode52_totalNQueen(n int) int {
	matrix := make([][]byte, n)
	for i:=0; i<n; i++ {
		matrix[i] = make([]byte, n)
		for j:=0; j<n; j++ {
			matrix[i][j] = '.'
		}
	}

	var valid func(row, col int) bool
	var solve func(row int)

	valid = func(row, col int) bool {
		for i:=0; i<row; i++ {
			if matrix[i][col] == 'Q' {
				return false
			}
		}

		i, j := row-1, col+1
		for {
			if i<0 || j >= n {
				break
			}
			if matrix[i][j] == 'Q' {
				return false
			}
			i--
			j++
		}
		i, j = row-1, col-1
		for {
			if i<0 || j<0 {
				break
			}
			if matrix[i][j] == 'Q' {
				return false
			}
			i--
			j--
		}
		return true
	}
	total := 0
	solve = func(row int) {
		if row == n {
			total++
			return
		}
		for col :=0; col<n; col++ {
			if valid(row, col) {
				matrix[row][col] = 'Q'
				solve(row+1)
				matrix[row][col] = '.'
			}
		}
	}

	solve(0)
	return total
}

// 53. 最长子序列和
func Leecode53_maxSubArray(nums []int) int {
	// 动态规划
	max, pre := nums[0], 0
	for _, n := range nums {
		pre = common.Max(pre+n, n)
		max = common.Max(max, pre)
	}
	return max
}

// 分治 + 回溯
func Leecode53_maxSubArray2(nums []int) int {
	type Status struct {
		lSum, rSum, mSum, iSum int
	}
	var getInfo func(left, right int) Status
	var pushUp func(left, right Status) Status

	getInfo = func(left, right int) Status {
		if left == right {
			return Status{nums[left], nums[left], nums[left], nums[left]}
		}
		m := (left + right) >> 1 // 相当于 (left+right) / 2
		leftStatus := getInfo(left, m) // 计算左半边的和
		rightStatus := getInfo(m+1, right) // 计算右半边的和
		return pushUp(leftStatus, rightStatus)
	}

	pushUp = func(left, right Status) Status {
		iSum := left.iSum + right.iSum
		lSum := common.Max(left.lSum, left.lSum + right.lSum)
		rSum := common.Max(right.rSum, left.rSum + right.rSum)
		mSum := common.Max(common.Max(left.mSum, right.mSum), left.rSum + right.lSum)
		return Status{lSum: lSum, iSum: iSum, rSum: rSum, mSum: mSum}
	}
	return getInfo(0, len(nums)-1).mSum
}

// 54. 螺旋矩阵

func Leecode54_spiralOrder(matrix [][]int) []int{
	var result []int
	m, n := len(matrix), len(matrix[0])
	left, right, top, bottom := 0, n-1, 0, m-1
	fmt.Println(m, n)
	for left <= right && top <= bottom {
		for i:=left; i<right; i++ {
			result = append(result, matrix[top][i])
		}
		for j:=top; j<bottom; j++ {
			result = append(result, matrix[j][right])
		}
		for k:=right; k>left; k-- {
			result = append(result, matrix[bottom][k])
		}
		for n:=bottom; n>top; n-- {
			//fmt.Println(n, left)
			result = append(result, matrix[n][left])
		}
		left++
		right--
		top++
		bottom--
	}
	fmt.Println(left, right, top, bottom)
	if left == right && left == top {
		result = append(result, matrix[left][left])
	}
	return result
}

// 57. 插入区间
func Leecode57_insert(intervals [][]int, newintervals [][]int) [][]int {
	// TODO
	return nil
}

// 58. 最后一个单词长度
// 时间复杂度： O(n)
func Leecode58_lengthOfLastWord(s string) int {
	isWord := func(c uint8) bool {
		if (c >= 'A' && c <='Z') || (c >= 'a' && c <= 'z') {
			return true
		}
		return false
	}
	start, word := 0, false
	max := 0
	for i:=0; i<len(s); i++ {
		if s[i] == ' ' {
			if max < i-start{
				if word {
					max = i-start
				}
			}
			start = i
			continue
		}
		if i == len(s) - 1 {
			if max < i-start {
				if word {
					max = i-start
				}
			}
		}
		if isWord(s[i]) {
			word = true
		} else {
			word = false
		}
		fmt.Printf("%d, %c, %d, %v\n", i, s[i], start, word)
	}

	return max
}

// 59. 螺旋矩阵2
// 回旋算法
// 空间：O(1)
func Leecode59_generateMatrix(n int) [][]int {
	result := make([][]int, n)
	for i:=0; i<n; i++ {
		result[i] = make([]int, n)
	}
	left, right, top, bottom := 0, n-1, 0, n-1
	num := 0
	for left < right && top < bottom {
		for i:=left; i<right; i++ {
			num++
			result[top][i] = num
		}
		for j:=top; j<bottom; j++ {
			num++
			result[j][right] = num
		}
		for k:=right; k>left; k-- {
			num++
			result[right][k] = num
		}
		for n:=bottom; n>top; n-- {
			num++
			result[n][left] = num
		}
		left++
		right--
		top++
		bottom--
	}
	if n % 2 == 1 {
		result[left][top] = num+1
	}
	return result
}

// 56. 合并数组区间
func Leecode56_merge(intervals [][]int) [][]int {
	// 先将数组排序
	sort.SliceStable(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0]
	})
	var result [][]int
	size := len(intervals)
	i, j := 0, 0
	for i=0; i<size; i++ {
		result = append(result, intervals[i])
		for j=i+1; j<size; j++ {
			if intervals[i][1] <= intervals[j][0]  {
				result = append(result, intervals[j])
				break
			}
			if intervals[i][1] < intervals[j][1] {
				intervals[i][1] = intervals[j][1]
			}
		}

		i = j
	}
	return result
}
